package com.zjsru.oneDay202206;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: likew
 * @Date: 2022/7/3
 * 下一个更大元素 III
 *
 * 给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。
 *
 * 输入：n = 12
 * 输出：21
 *
 * 输入：n = 21
 * 输出：-1
 */
public class nextGreaterElement {
    public int nextGreaterElement(int n) {
        List<Integer> list = new ArrayList<>();
        while(n != 0){
            list.add(n % 10);
            n /= 10;
        }
        int len = list.size(), idx = -1;
        for (int i = 0; i < len - 1 && idx == -1; i++) {
            if(list.get(i + 1) < list.get(i)) idx = i + 1;
        }
        if(idx == -1) return -1;
        for (int i = 0; i < idx; i++) {
            if(list.get(i) > list.get(idx)){
                swap(list,i,idx);
                break;
            }
        }
        for (int l = 0, r = idx -1; l < r; l++,r--) {
            swap(list,l,r);
        }
        long ans = 0;
        for (int i = len - 1; i >= 0 ; i--) {
            ans = ans * 10 + list.get(i);
        }
        return ans > Integer.MAX_VALUE ? -1 : (int) ans;
    }
    
    private void swap(List<Integer> list, int a, int b) {
        int c = list.get(a);
        list.set(a,list.get(b));
        list.set(b,c);
    }
    
    public static void main(String[] args) {
        nextGreaterElement nextGreaterElement = new nextGreaterElement();
        int n = 12;
        System.out.println(nextGreaterElement.nextGreaterElement(n));
    }
}
